#ifdef KITSCHY_DEBUG_MEMORY 
#include "debug_memorymanager.h"
#endif

#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#include <time.h>
#endif
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stdarg.h"
#include "math.h"

#include "BList.h"

#include "symbol.h"
#include "sort.h"
#include "ontology.h"
#include "featureterm.h"
#include "FTKBase.h"
#include "AUfeatureterm.h"
#include "FT_refinement.h"
#include "FT_generalization.h"

#include "entropy.h"


#include "psm.h"


Prediction *refinement_LID3(FeatureTerm *problem,List<FeatureTerm> *cases,Path *description_path,Path *solution_path,Ontology *o,FTKBase *domain_model,int heuristic,int selection_mode,int min_precedents)
{
	Prediction *prediction=0;
	List<FeatureTerm> *discriminant_set,*dset_tmp,*discriminant_set_complementary;
	List<FeatureTerm> *discriminant_solutions,*dsolutions_tmp;
	List<FeatureTerm> solutions;
	FeatureTerm *description,*solution;
	FeatureTerm *last_description,*current_description,*refinement;
	FeatureTerm *short_description;
	List<FeatureTerm> *description_refinements;
	int nrefinements,i,selected;
	float *heuristics;
	int *coverage;
	bool finished;

	int start_time=GetTickCount();
//	printf("rLID3: start\n");

	/* Create the initial description and discriminant sets: */ 
	current_description = new FeatureTerm((Symbol *)0,o->get_sort("any"),0);
	short_description = new FeatureTerm(current_description);
	{
		List<FeatureTerm> l;
		List<FeatureTerm> *l1,*l2;
		FeatureTerm *c;

		discriminant_set=new List<FeatureTerm>;
		discriminant_set_complementary=new List<FeatureTerm>;
		discriminant_solutions=new List<FeatureTerm>;

		l.Instance(*cases);
		l.Rewind();
		while(l.Iterate(c)) {
			l1=c->readPath(description_path);
			l2=c->readPath(solution_path);
			if (l1->Length()==1 && l2->Length()==1) {
				discriminant_set->Add(l1->ExtractIni());
				discriminant_solutions->Add(l2->ExtractIni());
			} /* if */ 
			delete l1;
			delete l2;
		} /* while */ 

//		printf("rLID3: %i initial cases\n",discriminant_set->Length());
	}


	/* Compute the different solutions: */ 
	{
		List<FeatureTerm> l;

//		printf("Solutions:\n");
		l.Instance(*discriminant_solutions);
		while(l.Iterate(solution)) {
			if (!solutions.MemberP(solution)) {
				solutions.Add(new FeatureTerm(solution));
/*				
				{
					char *s;
					s=solution->toStringNOOS();
					printf("%s\n",s);
					delete []s;
				}
*/
			} /* if */ 
		} /* while */ 
	}

	if (solutions.Length()==0) {
		printf("rLID3: ERROR!! no solutions!\n");
		delete current_description;
		delete discriminant_set;
		delete discriminant_set_complementary;
		delete discriminant_solutions;
		return 0;
	} /* if */ 

	do{
		finished=false;

		/* Description = Antiunification of all the base objects: */ 
		{
			List<FeatureTerm> tmp1,tmp2,tmp3;

			tmp1.Add(new FeatureTerm(problem));
			discriminant_set->Rewind();
			while(discriminant_set->Iterate(description)) tmp1.Add(new FeatureTerm(description));

			tmp2.Add(new FeatureTerm(current_description));

//			printf("rLID3: Antiunification with %i objects...\n",tmp1.Length());
			antiunification(&tmp3,&tmp1,SPECIALIZATION_LANGUAGE_AUTODETECT,&tmp2,o,domain_model,true,AU_VERSION_FAST);
//			antiunification(&tmp3,&tmp1,SPECIALIZATION_LANGUAGE_AUTODETECT,&tmp2,o,domain_model,false,AU_VERSION_FAST);
//			printf("rLID3: Antiunification complete\n",tmp1.Length());

			delete current_description;
			current_description=tmp3.ExtractIni();	
		}

/*
		{
			char *s;
			FeatureTerm *sol,*sol2;
			List<FeatureTerm> l,l2;
			int count;

			s=current_description->toStringNOOS(domain_model);
			printf("Justification:\n%s\n",s);
			delete []s;
			printf("Precedents: %i\n",discriminant_set->Length());

			l.Instance(solutions);
			l2.Instance(*discriminant_solutions);
			while(l.Iterate(sol)) {
				count=0;
				l2.Rewind();
				while(l2.Iterate(sol2)) if (*sol==*sol2) count++;

				s=sol->toNiceString();
				printf("%s - %i | ",s,count);
				delete []s;

			} // while  
			printf("\n");
		}		
*/		

//		printf("rLID3: Compute next refinements...\n");
		{
			List<FeatureTerm> objects;

			objects.Add(problem);
			discriminant_set->Rewind();
			while(discriminant_set->Iterate(description)) objects.Add(description);
//			description_refinements = DSpecializationL2(current_description,&objects,0,o,-1,domain_model);
			description_refinements = DSpecializationL2_b(current_description,&objects,0,o,domain_model);
			objects.ExtractAll();
		}
//		printf("rLID3: %i refinements\n",description_refinements->Length());

		/* Filter refinements: */ 
		{
			List<FeatureTerm> to_delete;
			bool valid;

			description_refinements->Rewind();
			while(description_refinements->Iterate(refinement)) {
				valid=false;

/*
				{
					char *s;
					s=refinement->toStringNOOS();
					printf("REFINEMENT:\n%s\n",s);
					delete []s;
				}
*/

				if (refinement->subsumes(problem) && !refinement->subsumes(current_description)) {
					valid=true;
//					discriminant_set->Rewind();
//					while(!valid && discriminant_set->Iterate(description)) 
//						if (refinement->subsumes(description)) valid=true;
				} /* if */ 

				if (!valid) to_delete.Add(refinement);

//				if (valid) printf("rLID3: valid\n");
			} /* while */ 

			while(!to_delete.EmptyP()) {
				refinement=to_delete.ExtractIni();
				description_refinements->DeleteElement(refinement);
				delete refinement;
			} /* while */ 
		}
//		printf("rLID3: %i valid refinements\n",description_refinements->Length());
		

		selected=-1;
		if (description_refinements->Length()>0) {

			/* Evaluate all the refinements: */ 
			nrefinements=description_refinements->Length();
			heuristics=new float[nrefinements];
			coverage=new int[nrefinements];
			description_refinements->Rewind();
			i=0;
//			printf("rLID3: Computing heuristics...\n");
			while(description_refinements->Iterate(refinement)) {
				switch(heuristic) {
				case 0:	/* Information Gain: */ 
						heuristics[i]=h_information_gain(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				case 1: /* RLDM: */ 
						heuristics[i]=1-h_rldm(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				case 2: /* Entropy: */ 
						heuristics[i]=h_entropy(discriminant_set,discriminant_solutions,&solutions,refinement,&(coverage[i]));
						break;
				default:coverage[i]=0;
						heuristics[i]=0;
						break;
				} /* switch */ 	
				
//				printf("%g [%i]\n",heuristics[i],coverage[i]);

				i++;
			} /* while */ 
//			printf("rLID3: heuristics complete\n");

			/* Choose one refinement: */ 
			switch(selection_mode) {
				case 0:/* MAXIMUM: */ 
					{
						int i;
						float maximum=heuristics[0];
						selected=0;

						for(i=1;i<nrefinements;i++) {
							if (heuristics[i]>maximum || (heuristics[i]==maximum && coverage[i]>coverage[selected])) {
								maximum=heuristics[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;
				case 1:/* RANDOM: */ 
					selected=rand()%nrefinements;
					break;
				case 2:/* RANDOM PONDERATED: */ 
					{
						int i;
						float h_sum=0;
						float tmp,accum;

//						printf("{ 0");
						for(i=0;i<nrefinements;i++) {
							h_sum+=heuristics[i];
//							printf(" - %g",h_sum);
						} /* if */ 
						tmp=(float(rand())*h_sum)/float(RAND_MAX);

						selected=-1;
						accum=0;
						for(i=0;selected==-1 && i<nrefinements;i++) {
							if (accum+heuristics[i]>tmp) selected=i;
							accum+=heuristics[i];
						} /* for */ 

//						printf(" } -> %g -> %i\n",tmp,selected);

						if (selected==-1) selected=rand()%nrefinements;
					}
					break;
				case 3:/* MINIMUM: */ 
					{
						int i;
						float minimum=heuristics[0];
						selected=0;

						for(i=1;i<nrefinements;i++) {
							if (heuristics[i]<minimum || (heuristics[i]==minimum && coverage[i]>coverage[selected])) {
								minimum=heuristics[i];
								selected=i;
							} /* if */ 
						} /* for */  
					}
					break;

				default:
					selected=0;
					break;
			} /* while */ 

			delete []heuristics;
			delete []coverage;
		} /* if */ 

		if (selected>=0) {
//			printf("rLID3: filtering discriminant set...\n");

			last_description=current_description;
			current_description=new FeatureTerm(description_refinements->operator [](selected));
/*
			{
				printf("rLID3: selected refinement %i\n",selected);
				char *s;
				s=current_description->toStringNOOS(domain_model);
				printf("%s\n",s);
				delete []s;
			}
*/

			dset_tmp=new List<FeatureTerm>;
			dsolutions_tmp=new List<FeatureTerm>;

			discriminant_set->Rewind();
			discriminant_solutions->Rewind();
			while(discriminant_set->Iterate(description) &&
				  discriminant_solutions->Iterate(solution)) {
				if (current_description->subsumes(description)) {
					dset_tmp->Add(new FeatureTerm(description));
					dsolutions_tmp->Add(new FeatureTerm(solution));
				} else {
/*
					{
						printf("rLID3: problem NOT subsumed %i\n",selected);
						char *s;
						s=description->toStringNOOS(domain_model);
						printf("%s\n",s);
						delete []s;
					}
*/
				   discriminant_set_complementary->Add(new FeatureTerm(description));
				} /* if */ 
			} /* while */ 

//			printf("rLID: |Dset| = %i, |DsetC| = %i\n",dset_tmp->Length(),discriminant_set_complementary->Length());

			if (dset_tmp->Length()>0) {
				delete last_description;
				delete discriminant_set;
				delete discriminant_solutions;
				discriminant_set=dset_tmp;
				discriminant_solutions=dsolutions_tmp;
				dset_tmp=0;
				dsolutions_tmp=0;
			} else {
//				printf("rLID3: discarting all the refinements\n");
		
				delete current_description;
				current_description=last_description;
				delete dset_tmp;
				delete dsolutions_tmp;
				dset_tmp=0;
				dsolutions_tmp=0;

				selected=-1;	/* Don't select this refinement, since it makes de discriminant set to be empty */ 
			} /* if */ 
		} /* if */ 

		delete description_refinements;

//		printf("rLID3: generalizing description...\n");
		/* Compute the new SHORT description: */ 
		{
			List<FeatureTerm> l3;
			List<FeatureTerm> *l,l2;
			FeatureTerm *f,*f2,*d;
			bool end,c1,c2;

			l2.Add(new FeatureTerm(short_description));
			f=new FeatureTerm(current_description);

			do{
				end=true;
//				l=DGeneralization(f,&l2,o,domain_model);
				l=DGeneralization(f,o,domain_model);

				l->Rewind();
				while(l->Iterate(f2) && end) {
					
					c1=true;
					l3.Instance(*discriminant_set);
					l3.Rewind();
					while(l3.Iterate(d) && c1) {
						if (!f2->subsumes(d)) c1=false;
					} /* while */ 

					c2=true;
					l3.Instance(*discriminant_set_complementary);
					l3.Rewind();
					while(l3.Iterate(d) && c2) {
						if (f2->subsumes(d)) c2=false;
					} /* while */ 

					if (c1 && c2) {
						delete f;
						f=new FeatureTerm(f2);
						end=false;
					} /* if */ 
				} /* if */ 
				delete l;
			}while(!end);
			delete short_description;
			short_description=f;

			/*

				short_description = the more general generalization of "current_description" such that:
					- subsumes all positive examples
					- does not subsume any negative example
					- is more specific than last_short_description
			*/ 
		}
//		printf("rLID3: generalization complete.\n");


		if (selected>=0) {
			List<FeatureTerm> l,stmp;

//			printf("Candidate solutions: ");
			l.Instance(*discriminant_solutions);
			while(l.Iterate(solution)) {
				if (!stmp.MemberP(solution)) {
					stmp.Add(new FeatureTerm(solution));
/*
					{
						char *s;
						s=solution->toNiceString();
						printf("%s ",s);
						delete []s;
					}
*/
				} /* if */ 
			} /* while */ 
//			printf("\n");

			if (stmp.Length()==1) finished=true;
		} /* if */ 

		if (discriminant_set->Length()<min_precedents) finished=true;
	}while(selected>=0 && !finished);

	/* Determine final solution: */ 
	prediction=new Prediction(new FeatureTerm(problem));
	{
		int i;
		List<FeatureTerm> l;
		int *distribution=new int[solutions.Length()];

		for(i=0;i<solutions.Length();i++) distribution[i]=0;

		l.Instance(*discriminant_solutions);
		while(l.Iterate(solution)) {
			distribution[solutions.Position(solution)]++;
		} /* while */ 

		for(i=0;i<solutions.Length();i++) {
			if (distribution[i]>0) {
				prediction->justifications.Add(new FeatureTerm(short_description));
				prediction->solutions.Add(new FeatureTerm(solutions[i]));
				prediction->support.Add(new int(distribution[i]));		
			} /* if */ 
		} /* for */ 
		delete []distribution;

		// Sort the solutions according to their support:
		{
			int i;
			bool change;
			int *iptr;
			FeatureTerm *ftptr;
			do{
				change=false;
				for(i=0;i<prediction->justifications.Length()-1;i++) {
					if (*(prediction->support[i])<*(prediction->support[i+1])) {
						iptr=prediction->support[i];
						prediction->support.SetObj(i,prediction->support[i+1]);
						prediction->support.SetObj(i+1,iptr);

						ftptr=prediction->solutions[i];
						prediction->solutions.SetObj(i,prediction->solutions[i+1]);
						prediction->solutions.SetObj(i+1,ftptr);

						ftptr=prediction->justifications[i];
						prediction->justifications.SetObj(i,prediction->justifications[i+1]);
						prediction->justifications.SetObj(i+1,ftptr);
						change=true;
					} // if 
				} // for 
			}while(change);
		}
	} /* if */ 


	/* Show result: */ 
	{
		char *s;
		FeatureTerm *j,*sol;
		int *sup;
		printf("/- rLID3 --------------------------------------------------------\\\n");
		printf("* Time taken: %ims\n",GetTickCount()-start_time);
		printf("* Problem:\n");
		if (prediction->problem->getName()!=0) {
			s=prediction->problem->getName()->get();
			printf("  %s\n",s);
		} else {
			printf("?\n");
		} // if
		printf("* %i different solutions\n",prediction->justifications.Length());
		prediction->justifications.Rewind();
		prediction->solutions.Rewind();
		prediction->support.Rewind();
		while(prediction->justifications.Iterate(j) &&
			  prediction->solutions.Iterate(sol) &&
			  prediction->support.Iterate(sup)) {
			printf("* Solution:\n");
			s=sol->toStringNOOS(domain_model);
			printf("  %s\n",s);
			delete []s;
			printf("* Justification:\n");
			s=j->toStringNOOS(domain_model);
			printf("%s\n",s);
			delete []s;
			printf("* Support: %i\n",*sup);
		} // while 
		printf("\\----------------------------------------------------------------/\n");
	}

	delete short_description;
	delete current_description;
	delete discriminant_set;
	delete discriminant_set_complementary;
	delete discriminant_solutions;

	return prediction;
} /* refinement_LID3 */ 






